#undef NDEBUG
#include<assert.h>
typedef struct Sub_Poly_Ver{
    double* p;
    int i;
    double t;
}Sub_Poly_Ver;
static inline void sub_poly_ver_init(Sub_Poly_Ver* spv)
{
    spv->p=NULL;
    spv->i=0;
    spv->t=0;
}

static double compute_one_angle(double *p1,double* p2,double*p3,double* n)
{
    double dir1[3]={p3[0]-p2[0],p3[1]-p2[1],p3[2]-p2[2]};
    double dir2[3]={p1[0]-p2[0],p1[1]-p2[1],p1[2]-p2[2]};

    if(!normalize(dir1,3)||!normalize(dir2,3))
    {
        return 0;
    }
    double* n1=out_product(dir1,dir2);
    double score=inner_product(dir1,dir2,3);
    score=1-score;
    if(inner_product(n1,n,3)<0)
    {
        score=score-2;
    }
    free(n1);
    return score;
}

static double compute_score_in_polygon1(double**v,int len,double* n,int i)
{
    int trian[3]={0};
    trian[0]=i; trian[1]=(i+1)%len;trian[2]=(i-1+len)%len;
    double score=compute_one_angle(v[trian[0]],v[trian[1]],v[trian[2]],n);

    if(score<0){return score;}

    trian[0]=(i+1)%len; trian[1]=(i-1+len)%len;trian[2]=i;
    double temp_score=compute_one_angle(v[trian[0]],v[trian[1]],v[trian[2]],n);
    if(temp_score<score)
    {
        score=temp_score;
    }
    if(score<0){return score;}
    trian[0]=(i-1+len)%len; trian[1]=(i+1)%len;trian[2]=(i+2)%len;
    temp_score=compute_one_angle(v[trian[0]],v[trian[1]],v[trian[2]],n);
    if(temp_score<score)
    {
        score=temp_score;
    }
    if(score<0){return score;}

    trian[0]=(i-2+len)%len; trian[1]=(i-1+len)%len;trian[2]=(i+1)%len;
    
    temp_score=compute_one_angle(v[trian[0]],v[trian[1]],v[trian[2]],n);
    if(temp_score<score)
    {
        score=temp_score;
    }
    if(score<0){return score;}

    int j=(i-1+len)%len,k=(i+1)%len;
    for(int ii=0;ii<len;ii++)
    {
        if(ii==i||ii==j||ii==k||
            ii==(i-2+len)%len||ii==(i+2)%len
            ){continue;}
        double dir1[3]={v[ii][0]-v[j][0],v[ii][1]-v[j][1],v[ii][2]-v[j][2]};
        double dir2[3]={v[ii][0]-v[i][0],v[ii][1]-v[i][1],v[ii][2]-v[i][2]};
        double dir3[3]={v[ii][0]-v[k][0],v[ii][1]-v[k][1],v[ii][2]-v[k][2]};
        double*tn1=out_product(dir1,dir2);
        double* tn2=out_product(dir2,dir3);
        double* tn3=out_product(dir3,dir1);
        if(inner_product(tn1,tn2,3)>=0&&inner_product(tn1,tn3,3)>=0
            &&inner_product(tn2,tn3,3)>=0)
        {
            score=-1;
        }
        free(tn1);free(tn2);free(tn3);
        if(score<=-1){break;}
    }
    return score;
}

// 修改，分数应该是新添加两点的新角度的最小角作为分数，并选择最大分数
//*
static double compute_score_in_polygon(double**v,int len,double* n,int i)
{
    int j=(i-1+len)%len,k=(i+1)%len;
    double a[3]={v[i][0]-v[j][0],v[i][1]-v[j][1],v[i][2]-v[j][2]};
    double b[3]={v[k][0]-v[i][0],v[k][1]-v[i][1],v[k][2]-v[i][2]};
    if(!normalize(a,3)||!normalize(b,3))
    {
        return -1;
    }
    double* n1=out_product(a,b);
    double score=inner_product(a,b,3);
    if(inner_product(n1,n,3)<0)
    {
        score=score-2;
    }
    else
    {
        score=-score;
    }
    free(n1);
    if(score<-1){return score;}
    for(int ii=0;ii<len;ii++)
    {
        if(ii==i||ii==j||ii==k){continue;}
        double dir1[3]={v[ii][0]-v[j][0],v[ii][1]-v[j][1],v[ii][2]-v[j][2]};
        double dir2[3]={v[ii][0]-v[i][0],v[ii][1]-v[i][1],v[ii][2]-v[i][2]};
        double dir3[3]={v[ii][0]-v[k][0],v[ii][1]-v[k][1],v[ii][2]-v[k][2]};
        double*tn1=out_product(dir1,dir2);
        double* tn2=out_product(dir2,dir3);
        double* tn3=out_product(dir3,dir1);
        if(inner_product(tn1,tn2,3)>=0&&inner_product(tn1,tn3,3)>=0
            &&inner_product(tn2,tn3,3)>=0)
        {
            score=-1;
        }
        free(tn1);free(tn2);free(tn3);
        if(score<=-1){break;}

    }
    return score;
}

static void subdivision_of_polygon1( Sub_Poly_Ver* spvs,int len,int **s,double* n)
{
    if(len<3)
    {
        return ;
    }
    if(len==3)
    {
        s[0][0]=spvs[0].i;
        s[0][1]=spvs[1].i;
        s[0][2]=spvs[2].i;
        return ;
    }


    double** v=(double**)malloc(sizeof(double*)*len);
    for(int i=0;i<len;i++)
    {
        v[i]=spvs[i].p;
       // printf("%lf %lf %lf\n",v[i][0],v[i][1],v[i][2]);
    } 
    //double *scores=(double*)malloc(sizeof(double)*len);
    int an=-1;double temp_score=-2;
    for(int i=0;i<len;i++ )
    {
        double score=compute_score_in_polygon1(v,len, n,i);
        // printf("spvs i:%d score:%lf\n",spvs[i].i,score);

        if(score>temp_score)
        {
            an=i;
            temp_score=score;
        }
    }

    free(v);
    //free(scores);
    //printf("an:%d\n",an);

    if(an==-1){return;}

   // printf("here1\n");
    int ia=(an-1+len)%len,ib=(an+1+len)%len; 
    s[0][0]=spvs[ia].i;
    s[0][1]=spvs[an].i;
    s[0][2]=spvs[ib].i;
    
    int temp_i=0;
    Sub_Poly_Ver* spvs1=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(len-1));
    for(int i=0;i<len;i++)
    {
        if(i==an)
        {
            continue;
        }
        spvs1[temp_i]=spvs[i];
        temp_i++; 
    }
    subdivision_of_polygon1(spvs1,len-1,&(s[1]),n);
    free(spvs1);
}

//修改
static inline int is_three_point_in_one_line(double* p1,double* p2,double* p3)
{
    //assert(false);
    double temp_p1[3]={p2[0]-p1[0],p2[1]-p1[1],p2[2]-p1[2]};
    double temp_p2[3]={p3[0]-p1[0],p3[1]-p1[1],p3[2]-p1[2]};
    //normalize 
    double* p= out_product(temp_p1,temp_p2);
    int re=0;
    if(inner_product(temp_p1,temp_p2,3)<0 &&lb_norm(p,3)<1e-7)
    {re=1;}

    SAFE_FREE(p);   
    return re; 
}
// p1 p2 p3按顺序

static inline int is_opt_sub_opt_vertex(double* p1,double* p2,double* p3,double* n)
{
    double temp_p1[3]={p1[0]-p2[0],p1[1]-p2[1],p1[2]-p2[2]};
    double temp_p2[3]={p3[0]-p2[0],p3[1]-p2[1],p3[2]-p2[2]};
    //normalize 
    double* p= out_product(temp_p2,temp_p1);
    int re=0;
    if(inner_product(p,n,3)<0)
    {
        re=0;
    }
    else{
        if(!normalize(temp_p1,3)||!normalize(temp_p2,3))
        {
            re=1;
        }
        else if(inner_product(temp_p1,temp_p2,3)<-0.98)
        {
            re=1;
        }
    }

    SAFE_FREE(p);
    return re;
}
// static int is_two_tri_connected(int* s1,int* s2)
// {
//     int num=0;
//     for(int i=0;i<3;i++)
//     {
//         for(int j=0;j<3;j++)
//         {
//             if(s1[i]==s2[j]){
//                 num++;     
//                 break;}
//         }
//     }
//     if(num==2){return 1;}
//     return 0;
// }

static int is_subv_in_polygon1(int id1,int id,int id2, Sub_Poly_Ver* spvs,int len ,double*n)
{
    int re=-1;
    for(int i=0;i<len;i++)
    {
        if(id1==spvs[i].i&&id==spvs[(i+1)%len].i&&id2==spvs[(i+2)%len].i )
        {
            re=i;break;
        }
    }
    if(re!=-1)
    {
        double dir1[3]={spvs[(re+1)%len ].p[0]-spvs[re].p[0],spvs[(re+1)%len ].p[1]-spvs[re].p[1], spvs[(re+1)%len ].p[2]-spvs[re].p[2] };
        double dir2[3]={spvs[(re+2)%len ].p[0]-spvs[re].p[0],spvs[(re+2)%len ].p[1]-spvs[re].p[1], spvs[(re+2)%len ].p[2]-spvs[re].p[2] };
        double* ou=out_product(dir1,dir2);
        if(inner_product(ou,n,3)<0)
        {
            re=1;
        }
        else{re=0;}
        free(ou);
        return re;
    }
    return 0;
}
//
//修改，调整法向相反的三角
//

static int is_finding_tri(Sub_Poly_Ver* spvs,int len,int *s,double* n,int* id1,int* id,int*id2)
{
    *id1=-1;*id=-1;*id2=-1;
    for(int i=0;i<3;i++)
    {
        if(is_subv_in_polygon1(s[(i+2)%3],s[i],s[(i+1)%3],spvs,len,n))
        {
            *id1=s[(i+2)%3];*id=s[i];*id2=s[(i+1)%3];
            return 1;
        }
    }   
    return 0;
}

static int my_tiaozhen_boundaries_tris(int * s1,int* s2,int id1,int id,int id2)
{
    int id3=-1;
    int num=0;
    for(int i=0;i<3;i++)
    {
        if(s2[i]==id1||s2[i]==id2)
        {
            num++;
        }
        else if(s2[i]!=id)
        {
            id3=s2[i];
        }
    }
    if(id3!=-1&&num==2)
    {
        s1[0]=id1;s1[1]=id;s1[2]=id3;
        s2[0]=id;s2[1]=id2;s2[2]=id3;
        return 1;
    }
    return 0;

}

static void tiaozheng_boundaries_tris( Sub_Poly_Ver* spvs,int len,int **s,double* n)
{
    int id1=-1,id=-1,id2=-1;
    for(int i=0;i<len-2;i++)
    {
        if(is_finding_tri(spvs,len,s[i],n,&id1,&id,&id2))
        {
            for(int j=0;j<len-2;j++)
            {
                if(i!=j&& my_tiaozhen_boundaries_tris(s[i],s[j],id1,id,id2))
                {
                    break;
                }
            }
        }
    }
}

static void optimization_subdivision_of_polygon1( Sub_Poly_Ver* spvs,int len,int **s,double* n)
{
    if(len<3){return;}
    if(len==3){
        s[0][0]=spvs[0].i;
        s[0][1]=spvs[1].i;
        s[0][2]=spvs[2].i;
        return ;
    }
    
    Sub_Poly_Ver spv,spv1,spv2;
    spv.i=-1;spv1.i=-1,spv2.i=-1;
    // for(int i=0;i<len;i++)
    // {
    //     // 修改为1e-4 怎么样//
    //     //
    //     if(distance_of_two_points(spvs[i].p, spvs[(i+1)%len].p,3)<1e-3 )
    //     {
    //         spv2=spvs[(i-1+len)%len];
    //         spv=spvs[i];
    //         spv1=spvs[(i+1)%len];
    //         break;
    //     }
    // }
    if(spv.i==-1)
    {
        for(int i=0;i<len;i++)
        {
            if(is_opt_sub_opt_vertex( spvs[(i-1+len)%len].p,spvs[i].p,spvs[(i+1)%len].p,n) )
            {
                spv2=spvs[(i-1+len)%len];
                spv=spvs[i];
                spv1=spvs[(i+1)%len];
                break;
            }
        }
    }

    if(spv.i==-1)
    {
        subdivision_of_polygon1(spvs,len,s,n); 
    }
    else
    {
        printf("opt sub i:%d %d %d\n",spv.i,spv1.i,spv2.i);
        Sub_Poly_Ver* spvs1=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(len-1));
        int temp_i=0;
        for(int i=0;i<len;i++)
        {
            if(spvs[i].i!=spv.i)
            {
                spvs1[temp_i]=spvs[i];
                temp_i++;
            }
        }

        optimization_subdivision_of_polygon1(spvs1,len-1,s,n);

        for(int i=0;i<len-3;i++)
        {
            if(s[i][0]==spv2.i&&s[i][1]==spv1.i)
            {
                s[len-3][0]=spv.i;s[len-3][1]=s[i][1];s[len-3][2]=s[i][2];

                s[i][1]=spv.i;

                ///printf("hre1\n");
                break;
            }
            else if(s[i][1]==spv2.i&&s[i][2]==spv1.i)
            {
                s[len-3][0]=s[i][0];s[len-3][1]=spv.i;s[len-3][2]=s[i][2];

                s[i][2]=spv.i;

                //printf("hre2\n");

                break;
            }
            else if(s[i][2]==spv2.i&&s[i][0]==spv1.i)
            {
                s[len-3][0]=s[i][0];s[len-3][1]=s[i][1];s[len-3][2]=spv.i;

                s[i][0]=spv.i;
                //printf("hre3\n");

                break;
            }
        }
        free(spvs1);
    }

}

static int is_edge_inter_with_triangle(Sub_Poly_Ver* edge,Sub_Poly_Ver spv1,
    Sub_Poly_Ver spv2,Sub_Poly_Ver spv3,double* n)
{
    if((edge[0].i==spv1.i&&edge[1].i==spv2.i)||(edge[1].i==spv1.i&&edge[0].i==spv2.i) )
    {
        return 2;
    }
    else if((edge[0].i==spv2.i&&edge[1].i==spv3.i)||(edge[1].i==spv2.i&&edge[0].i==spv3.i))
    {
        return 2;

    }
    else if((edge[0].i==spv1.i&&edge[1].i==spv3.i)||(edge[1].i==spv1.i&&edge[0].i==spv3.i))
    {
        return 2;
    }
    else if(edge[0].i==spv1.i||edge[0].i==spv2.i||edge[0].i==spv3.i||
        edge[1].i==spv1.i||edge[1].i==spv2.i||edge[1].i==spv3.i)
    {
        return 1;
    }
    //Sub_Poly_Ver* spvs[3]={&spv1,&spv2,&spv3};
    // for(int i=0;i<2;i++)
    // {
    //     for(int j=0;j<3;j++)
    //     {
    //         if(edge[i].i==spvs[j]->i)
    //         {
    //             double dir1[3]={spvs[(j+2)%3]->p[0]-spvs[(j)%3]->p[0],
    //                 spvs[(j+2)%3]->p[1]-spvs[(j)%3]->p[1], spvs[(j+2)%3]->p[2]-spvs[(j)%3]->p[2]};
                
    //             double dir2[3]={edge[(i+1)%2].p[0]-spvs[(j)%3]->p[0],
    //                 edge[(i+1)%2].p[1]-spvs[(j)%3]->p[1], edge[(i+1)%2].p[2]-spvs[(j)%3]->p[2]};
    //             double dir3[3]={spvs[(j+1)%3]->p[0]-spvs[(j)%3]->p[0],
    //                 spvs[(j+1)%3]->p[1]-spvs[(j)%3]->p[1], spvs[(j+1)%3]->p[2]-spvs[(j)%3]->p[2]};
                
    //             double *ou1=out_product(dir2,dir1);
    //             double* ou2=out_product(dir3,dir2);
    //             int re=0;
    //             if(inner_product(ou1,n,3)>0&&inner_product(ou2,n,3)>0)
    //             {
    //                 re=1;
    //             }
    //             free(ou1);free(ou2);
    //             return re;
    //         }
    //     }
    // }

    double *l =get_line_equation_from_two_points(edge[0].p,edge[1].p);
    if(l==NULL)
    {
        double dir1[3]={edge[0].p[0]-spv1.p[0],edge[0].p[1]-spv1.p[1],edge[0].p[2]-spv1.p[2]};
        double dir2[3]={edge[0].p[0]-spv2.p[0],edge[0].p[1]-spv2.p[1],edge[0].p[2]-spv2.p[2]};
        double dir3[3]={edge[0].p[0]-spv3.p[0],edge[0].p[1]-spv3.p[1],edge[0].p[2]-spv3.p[2]};
        double* tn1=out_product(dir1,dir2);
        double* tn2=out_product(dir2,dir3);
        double* tn3=out_product(dir3,dir1);
        int re=0;
        if(inner_product(tn1,tn2,3)>=0&&inner_product(tn1,tn3,3)>=0
            &&inner_product(tn2,tn3,3)>=0)
        {
            re=1;
        }
        free(tn1);free(tn2);free(tn3);
        return re;
    }
    else
    {
        double *tri[3]={spv1.p, spv2.p,spv3.p};
        double *t= line_intersection_with_polygon(l,tri ,3);
        double t1[2]={0-1e-6, distance_of_two_points(edge[0].p,edge[1].p,3)+1e-6 };
        free(l);
        int re=0;
        if(t==NULL)
        {re=0;}
        else 
        {
            if(t[1]<t1[0]||t[0]>t1[1])
            {
                re=0;
            }
            else
            {
                printf("t:%lf %lf %lf %lf\n",t1[0],t1[1],t[0],t[1]);
                re=1;
            }
            free(t);
        }
        return re;
    }
    return 0;
}

//修改
static int is_two_edge_intersecting(Sub_Poly_Ver* edge1,Sub_Poly_Ver*edge2)
{
    // double dir[3]={edge2[0].p[0]-edge2[1].p[0],edge2[0].p[1]-edge2[1].p[1], edge2[0].p[2]-edge2[1].p[2]};
    // normalize(dir,3);
    if((edge1[0].i==edge2[0].i&&edge1[1].i==edge2[1].i)||
        (edge1[0].i==edge2[1].i&&edge1[1].i==edge2[0].i))
    {
        return 1;
    }
    else if(edge1[0].i==edge2[0].i||edge1[1].i==edge2[0].i)
    {
        return is_point_in_line_segment(edge2[1].p,edge1[0].p ,edge1[1].p);
    }
    else if(edge1[0].i==edge2[1].i||edge1[1].i==edge2[1].i)
    {
        return is_point_in_line_segment(edge2[0].p,edge1[0].p ,edge1[1].p);
    }

    return is_line_segment_intersecting_with_line_segment(edge1[0].p,edge1[1].p,edge2[0].p ,
        edge2[1].p,NULL);

}

static int is_subv_in_polygon(Sub_Poly_Ver spv,Sub_Poly_Ver* polygon,int p_len )
{
    for(int i=0;i<p_len;i++)
    {
        if(spv.i==polygon[i].i)
        {
            return 1;
        }
    }
    return 0;
}

static int is_edge_intersecting_with_polygon(Sub_Poly_Ver spv1,Sub_Poly_Ver spv2,
    Sub_Poly_Ver* polygon,int p_len)
{
    Sub_Poly_Ver edge1[2]={spv1,spv2};

    for(int i=0;i<p_len;i++)
    {
        Sub_Poly_Ver edge2[2]={polygon[i],polygon[(i+1)%p_len] };
        if(is_two_edge_intersecting(edge1,edge2))
        {
            return 1;
        }
    }
    return 0;
}

static void show_sub_data(int** s,
    int s_len)
{
    for(int i=0;i<s_len;i++)
    {
        printf("%d %d %d\n",s[i][0],s[i][1],s[i][2]);
    }
}

static int is_triangle_clockwise(Sub_Poly_Ver spv1,Sub_Poly_Ver spv2,Sub_Poly_Ver spv3,double* n)
{
    double dir1[3]={spv1.p[0]-spv2.p[0],
        spv1.p[1]-spv2.p[1], spv1.p[2]-spv2.p[2]};
    double dir2[3]={spv3.p[0]-spv2.p[0],
        spv3.p[1]-spv2.p[1], spv3.p[2]-spv2.p[2]};
    
    double *ou=out_product(dir2,dir1);
    int re=1;
    if(inner_product(ou,n,3)<0){
        re=0;
    }
    free(ou);
    return re;   
}




static int insert_one_edge2_polygon(Sub_Poly_Ver*spvs,int len, double* n,int** s,
    int *s_len,Sub_Poly_Ver* edge,Sub_Poly_Ver* polygon,int p_len)
{
    
    if(p_len<3){return 0;}
    double dir[3]={edge[1].p[0]-edge[0].p[0],edge[1].p[1]-edge[0].p[1], edge[1].p[2]-edge[0].p[2]};

    Sub_Poly_Ver spv1=edge[0],spv2=edge[1];
    printf("begin inser polygon:%d %d\n",p_len,*s_len);
    // printf("spv1 spv2:%d %d\n",spv1.i,spv2.i);
    //修改寻找最值

    if(!is_subv_in_polygon(spv1,polygon,p_len))
    {
        double temp_score=0;
        spv1.i=-1;
        // double temp_score=dir[0]*(edge[0].p[0]- polygon[0].p[0])+
        //     dir[1]*(edge[0].p[1]- polygon[0].p[1])+dir[2]*(edge[0].p[2]- polygon[0].p[2]);
        // spv1=polygon[0];
        for(int i=0;i<p_len;i++)
        {
            if(polygon[i].i== spv2.i){continue;}
            double dir1[3]={edge[0].p[0]- polygon[i].p[0], 
                edge[0].p[1]- polygon[i].p[1],edge[0].p[2]- polygon[i].p[2] };
            double temp_score1=inner_product(dir,dir1,3);
            if(spv1.i==-1||temp_score1>temp_score)
            {
                spv1=polygon[i];temp_score=temp_score1;
                // if(!is_edge_intersecting_with_polygon(polygon[i],edge[0],polygon,p_len))
                // {
                //     spv1=polygon[i];
                //     break;
                // }
            }
        }
    }
    //printf("hrere\n");
    if(!is_subv_in_polygon(spv2,polygon,p_len))
    {
        // double temp_score=dir[0]*(edge[1].p[0]- polygon[0].p[0])+
        //     dir[1]*(edge[1].p[1]- polygon[0].p[1])+dir[2]*(edge[1].p[2]- polygon[0].p[2]);
        // spv2=polygon[0];
        double temp_score=0;
        spv2.i=-1;
        for(int i=0;i<p_len;i++)
        {
            if(polygon[i].i== spv1.i){continue;}

            double dir1[3]={edge[1].p[0]- polygon[i].p[0], 
                edge[1].p[1]- polygon[i].p[1],edge[1].p[2]- polygon[i].p[2] };
            double temp_score1=inner_product(dir,dir1,3);
            if(spv2.i==-1||temp_score1<temp_score)
            {
                spv2=polygon[i];temp_score=temp_score1;
                // if(!is_edge_intersecting_with_polygon(polygon[i],edge[1],polygon,p_len))
                // {
                //     spv2=polygon[i];
                //     break;
                // }
            }
        }
    }
    printf("spv1 spv2:%d %d\n",spv1.i,spv2.i);
    assert(spv1.i!=spv2.i);
    assert(is_subv_in_polygon(spv2,polygon,p_len));
    assert(is_subv_in_polygon(spv1,polygon,p_len));
    if(spv1.i==spv2.i)
    {
        // optimization_subdivision_of_polygon1(polygon,p_len,&(s[*s_len]),n);
        // *s_len=*s_len+p_len-2;
        return 0;
    }

    //assert(false); 
    // if(spv1.i==spv2.i){
    //     printf("cuowu\n");
        
    //     if(((double*)NULL)[0]==1)
    //     {
    //         printf("cuowu\n");
        
    //     }
    //     return; 
    // }
    //printf("spv1 spv2:%d %d\n",spv1.i,spv2.i);

    Sub_Poly_Ver* polygon1=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(p_len+2));
    int p_len1=0;
    polygon1[0]=spv1;p_len1++;
    if(spv1.i!=edge[0].i )
    {
        polygon1[p_len1]=edge[0];p_len1++;
    }

    polygon1[p_len1]=edge[1];p_len1++;
    if(spv2.i!=edge[1].i)
    {
        polygon1[p_len1]=spv2;p_len1++;
    }

    Sub_Poly_Ver* polygon2=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(p_len+2));
    int p_len2=p_len1;
    for(int i=0;i<p_len1;i++)
    {
        polygon2[i]=polygon1[p_len1-1-i];
    }

    for(int i=0;i<p_len;i++)
    {
        if(polygon[i].i==spv2.i)
        {
            for(int j=0;j<p_len;j++)
            {
                if(polygon[(i+j+1)%p_len ].i==spv1.i)
                {
                    break;
                }
                polygon1[p_len1]=polygon[(i+j+1)%p_len ];
                p_len1++;

            }
            break;
        }
    }

    for(int i=0;i<p_len;i++)
    {
        if(polygon[i].i==spv1.i)
        {
            for(int j=0;j<p_len;j++)
            {
                if(polygon[(i+j+1)%p_len ].i==spv2.i)
                {
                    break;
                }
                polygon2[p_len2]=polygon[(i+j+1)%p_len ];
                p_len2++;
            }
            break;
        }
    }

    //subdivision_of_polygon1(spvs_bound,bound_len,re,n); 

    //optimization_subdivision_of_polygon1(polygon1,p_len1,&(s[*s_len]),n);
    subdivision_of_polygon1(polygon1,p_len1,&(s[*s_len]),n);
    //tiaozheng_boundaries_tris( polygon1,p_len1,&(s[*s_len]), n);
    printf("once\n");
    *s_len=*s_len+p_len1-2;

    //optimization_subdivision_of_polygon1(polygon2,p_len2,&(s[*s_len]),n);
    subdivision_of_polygon1(polygon2,p_len2,&(s[*s_len]),n);
    //tiaozheng_boundaries_tris( polygon2,p_len2,&(s[*s_len]), n);

    *s_len=*s_len+p_len2-2;

    show_sub_data(s,*s_len);
    free(polygon1);
    free(polygon2);
    return 1;
}

static int is_two_tri_connected(int* s1,int* s2)
{
    int num=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(s1[i]==s2[j]){
                num++;     
                break;}
        }
    }
    if(num==2){return 1;}
    return 0;
    
}


static int max_num_connect_tri_marks(int** s,
    int s_len,int *tri_marks1)
{
    if(s_len<=0){return 0;}
    int* tri_marks=(int*)malloc(sizeof(int)*s_len);
    memmove(tri_marks,tri_marks1,sizeof(int)*s_len);
    int * re1=NULL;int temp_len=0,num=0;
    int flag=1;
    while(flag)
    {
        flag=0;
        int* temp_mark=NULL;
        int temp_len1=0;
        for(int i=0;i<s_len;i++)
        {
            if(tri_marks[i]==1)
            {
                temp_mark=(int*)malloc(sizeof(int)*s_len);
                memset(temp_mark,0,sizeof(int)*s_len);
                temp_mark[i]=1;
                tri_marks[i]=0;
                temp_len1++;
                //re=node_overlying(re,temp_mark);
                flag=1;
                break;
            }
        }

        if(temp_mark!=NULL)
        {
            num++;
            int flag1=1;
            while(flag1)
            {
                flag1=0;
                for(int i=0;i<s_len;i++)
                {
                    if(temp_mark[i]!=1)
                    {
                        continue;               
                    }
                    for(int j=0;j<s_len;j++)
                    {
                        if(i!=j&&tri_marks[j]==1&&is_two_tri_connected(s[i],s[j]))
                        {
                            flag1=1;
                            tri_marks[j]=0;
                            temp_mark[j]=1;temp_len1++;
                        }
                    }       
                }

            }
        }
        SAFE_FREE(temp_mark);
    }

    free(tri_marks);
    return num;
}
static int  chuli_connected_tria_marks1(int** s,
    int s_len,int *tri_marks)
{
    if(s_len<=0){return 0;}
    if(max_num_connect_tri_marks(s,s_len,tri_marks)==1)
    {
        return 1;
    }
    int* tri_marks1=(int*)malloc(sizeof(int)*s_len);
    for(int i=0;i<s_len;i++)
    {
        tri_marks1[i]=1;
    }
    //memmove(tri_marks1,tri_marks,sizeof(int)*s_len);
    int flag=1;
    while(flag)
    {
        flag=0;
        for(int i=0;i<s_len;i++)
        {
            if(tri_marks[i]==0&&tri_marks1[i]==1)
            {
                tri_marks1[i]=0;
                if(max_num_connect_tri_marks(s,s_len,tri_marks1)==1)
                {
                    flag=1;break;
                }
                else
                {
                    tri_marks1[i]=1;
                }
            }
        }

    }
    memmove(tri_marks,tri_marks1,sizeof(int)*s_len);
    free(tri_marks1);
    return 1;
}
static int  chuli_connected_tria_marks(int** s,
    int s_len,int *tri_marks)
{
    if(s_len<=0){return 0;}
    int* tri_marks1=(int*)malloc(sizeof(int)*s_len);
    memmove(tri_marks1,tri_marks,sizeof(int)*s_len);
    // for(int i=0;i<s_len;i++)
    // {
    //     tri_marks[i]=tri_marks1[i];
    // }
    int * re1=NULL;int temp_len=0;int num=0;
    int flag=1;
    while(flag)
    {
        flag=0;
        int* temp_mark=NULL;
        int temp_len1=0;
        for(int i=0;i<s_len;i++)
        {
            if(tri_marks[i]==1)
            {
                temp_mark=(int*)malloc(sizeof(int)*s_len);
                memset(temp_mark,0,sizeof(int)*s_len);
                temp_mark[i]=1;
                tri_marks[i]=0;
                temp_len1++;
                //re=node_overlying(re,temp_mark);
                flag=1;
                break;
            }
        }

        if(temp_mark!=NULL)
        {
            num++;
            int flag1=1;
            while(flag1)
            {
                flag1=0;
                for(int i=0;i<s_len;i++)
                {
                    if(temp_mark[i]!=1)
                    {
                        continue;               
                    }
                    for(int j=0;j<s_len;j++)
                    {
                        if(i!=j&&tri_marks[j]==1&&is_two_tri_connected(s[i],s[j]))
                        {
                            flag1=1;
                            tri_marks[j]=0;
                            temp_mark[j]=1;temp_len1++;
                        }
                    }       
                }

            }
        }
        if(temp_len<temp_len1)
        {
            temp_len=temp_len1;
            SAFE_FREE(re1);
            re1=temp_mark;
        }
        else
        {
            SAFE_FREE(temp_mark);
        }
    }

    if(re1!=NULL)
    {
        //memmove(tri_marks,re1,sizeof(int)*s_len);
        for(int i=0;i<s_len;i++)
        {
            printf("triansmkii:%d %d\n",re1[i],tri_marks1[i]);
            tri_marks[i]=re1[i];
        }
        SAFE_FREE(re1);
    }
    //assert(num==1);
    free(tri_marks1);
    return temp_len;
}

static void insert_one_edge2_mesh(Sub_Poly_Ver*spvs,int len,double* n, int** s,
    int *s_len,Sub_Poly_Ver* edge)
{

    if(*s_len<=0){return ;}
    int *tri_marks=(int*)malloc(sizeof(int)*(*s_len) );
    memset(tri_marks,0,sizeof(int)*(*s_len));
    for(int i=0;i<(*s_len);i++)
    {
        tri_marks[i]=is_edge_inter_with_triangle(edge,spvs[s[i][0]],
            spvs[s[i][1]],spvs[s[i][2]],n);
        if(tri_marks[i]==2)
        {
            free(tri_marks);
            return ;
        }
        if(tri_marks[i]==0)
        {
            if(!is_triangle_clockwise(spvs[s[i][0]],
                spvs[s[i][1]],spvs[s[i][2]],n))
            {
                tri_marks[i]=1;
            }
        }
        //printf("triansmki:%d\n",tri_marks[i]);
    }
   
    if(chuli_connected_tria_marks1(s,
            *s_len,tri_marks)<=0)
    {
        free(tri_marks);
        return ;
    }
 
    struct Sub_Poly_Edge{
        Sub_Poly_Ver spv1,spv2;
        int mark;
    };

    struct Sub_Poly_Edge*bound_edges=(struct Sub_Poly_Edge*)malloc(sizeof(struct Sub_Poly_Edge)*3*(*s_len) );
    int bound_edge_len=0;

    for(int i=0;i<(*s_len);i++)
    {
        if(tri_marks[i]==0){continue;}

        for(int j=0;j<3;j++)
        {
            int flag=0;
            for(int k=0;k< bound_edge_len;k++)
            {
                if(bound_edges[k].spv1.i==spvs[s[i][(j+1)%3]].i&&bound_edges[k].spv2.i==spvs[s[i][j]].i)
                {
                    bound_edges[k].mark+=1;
                    flag=1;
                    break;
                }
            }
            if(!flag)
            {
                bound_edges[bound_edge_len].spv1=spvs[s[i][j]];
                bound_edges[bound_edge_len].spv2=spvs[s[i][(j+1)%3]];
                bound_edges[bound_edge_len].mark=1;
                bound_edge_len++;
            }
        }
    }

// 提取边界 //
// 修改如果存在重复点怎么办, 严禁越界
// 修改，用图论的矩阵来做可以防止重复点越界

    int bound_edge_len1=0;
    int flag=1;
    Sub_Poly_Ver spv0;
    spv0.i=-1;

    while(flag)
    {
        flag=0;
        for(int i=bound_edge_len1;i<bound_edge_len;i++)
        {
            if(bound_edges[i].mark!=1)
            {
                continue;
            }
            if(spv0.i==-1||
                (spv0.i==bound_edges[i].spv1.i))
            {
                struct Sub_Poly_Edge temp=bound_edges[bound_edge_len1];
                bound_edges[bound_edge_len1]=bound_edges[i];
                bound_edges[i]=temp;
                spv0=bound_edges[bound_edge_len1].spv2;
                bound_edge_len1++;
                flag=1;
                break;
            }
        }
    }
    if(bound_edge_len1<=2){free(tri_marks);return;}
    printf("end tiqubian jie%d\n",bound_edge_len1);
    int** s_copy=(int**)malloc(sizeof(int*)*(*s_len));
    for(int i=0;i<(*s_len);i++)
    {
        s_copy[i]=(int*)malloc(sizeof(int)*3);
        s_copy[i][0]=s[i][0];
        s_copy[i][1]=s[i][1];
        s_copy[i][2]=s[i][2];
    }
    int s_len1=0;
    for(int i=0;i<(*s_len);i++)
    {
        if(tri_marks[i]==0)
        {
            s[s_len1][0]=s_copy[i][0];
            s[s_len1][1]=s_copy[i][1];
            s[s_len1][2]=s_copy[i][2];
            s_len1++;
        }
    }
    int s_len2=*s_len;
    *s_len=s_len1;
    assert(bound_edge_len1<=bound_edge_len);
    assert(s_len1<s_len2);
    //assert(false);
    Sub_Poly_Ver*bound_polygon=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*bound_edge_len1);
    int bound_edge_len2=0;
    for(int i=0;i<bound_edge_len1;i++)
    {
        if(is_subv_in_polygon(bound_edges[i].spv1,bound_polygon,bound_edge_len2))
        {
            continue;
        }
        bound_polygon[bound_edge_len2]=bound_edges[i].spv1;
        bound_edge_len2++;
        // if(bound_polygon[i].i>=len){printf("%d\n",bound_polygon[i].i);}
        // assert(bound_polygon[i].i<len);
        //printf("bianjie :%d\n",bound_polygon[i].i);
    }

    int insert_poly= insert_one_edge2_polygon(spvs,len, n,s,
        s_len,edge,bound_polygon,bound_edge_len2);

    if(insert_poly==0)
    {
        for(int i=0;i<s_len2;i++)
        {
            s[i][0]=s_copy[i][0];s[i][1]=s_copy[i][1];s[i][2]=s_copy[i][2];
        }
        *s_len=s_len2;
    }
    for(int i=0;i<s_len2;i++)
    {
        free(s_copy[i]);
    }

    free(bound_polygon);
    free(s_copy);
    free(tri_marks);
    free(bound_edges);
}

int** subdivision_of_polygon_with_edges1(double** v,int len, 
    int* bound,int bound_len,int**edges,int edge_len,int* re_len)
{
    printf("sub1***********\n");
    *re_len=0;
    if(len<3)
    {
        return NULL;
    }
    if(len==3)
    {
        if(bound_len<3){return NULL;}
        else
        {
            int ** re=(int**)malloc(sizeof(int*));
            re[0]=(int*)malloc(sizeof(int)*3);
            re[0][0]=bound[0];re[0][1]=bound[1];re[0][2]=bound[2];
            *re_len=1;
            return re;
        }
    }

    Sub_Poly_Ver* spvs=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*len);
    for(int i=0;i<len;i++)
    {
        spvs[i].p=v[i];
        spvs[i].i=i;
    }


    Sub_Poly_Ver* spvs_bound=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*bound_len);


    double **bound_v=(double**)malloc(sizeof(double*)*bound_len);

    for(int i=0;i<bound_len;i++)
    {
        spvs_bound[i]=spvs[bound[i]];
        bound_v[i]=v[bound[i]];
    }

    double * n=compute_plane_normal_of_jordan_curve(bound_v,bound_len);
    //normalize(n,3);
    free(bound_v);

    int ** re=(int**)malloc(sizeof(int*)*(bound_len+4*edge_len));

    for(int i=0;i<bound_len+4*edge_len;i++ )
    {
        re[i]=(int*)malloc(sizeof(int)*3);
        memset(re[i],0,sizeof(int)*3);
    }
    
    //subdivision_of_polygon1(spvs_bound,bound_len,re,n); 
    subdivision_of_polygon1(spvs_bound,bound_len,re,n);
    //optimization_subdivision_of_polygon1(spvs_bound,bound_len,re,n);
    *re_len=bound_len-2;
    show_sub_data(re,*re_len);
    
    for(int i=0;i<edge_len;i++)
    {
        Sub_Poly_Ver spvs_edge[2];
        spvs_edge[0]=spvs[edges[i][0]];
        spvs_edge[1]=spvs[edges[i][1]];
        printf("insert edge:%d %d\n",edges[i][0],edges[i][1]);
        insert_one_edge2_mesh(spvs,len,n, re,
            re_len,spvs_edge);
    }

    printf("shengyu :%d %d %d\n",bound_len+4*edge_len-*re_len,bound_len+4*edge_len,*re_len);
    show_sub_data(re,*re_len);
    assert(*re_len<bound_len+4*edge_len);
    for(int i=*re_len;i<bound_len+4*edge_len;i++)
    {
        free(re[i]);
    }

    free(spvs_bound);
    free(spvs);
    SAFE_FREE(n);

    return re;
    //return NULL;
}
//*************************************************************
//*************************************************************
/*
    以下是优化的代码剖分
*/
//****************************************
static int is_optimization_point_edge_id(Sub_Poly_Ver*spvs,int**edges_graph,
    int len,int id,int* id1,int* id2,Sub_Poly_Ver* bound,int bound_len )
{
    if(edges_graph[id][id]!=2){return 0;}

    *id1=-1;*id2=-1;
    for(int i=0;i<len;i++)
    {
        if(edges_graph[id][i]==1){
            *id1==-1?(*id1=i):(*id2=i);
        }
    }
    if(*id2==-1||*id2==id||*id1==id)
    {
        return 0;
    }
    // if(is_subv_in_polygon(spvs[*id1],bound,bound_len)&&
    //     is_subv_in_polygon(spvs[*id2],bound,bound_len) )
    // {
    //     return 1;
    // }
    // if(distance_of_two_points(spvs[id].p, spvs[*id1].p,3)<1e-3||
    //     distance_of_two_points(spvs[id].p,spvs[*id2].p,3)<1e-3)
    // {return 1;}
    
    return is_three_point_in_one_line(spvs[id].p,spvs[*id1].p,spvs[*id2].p);
}

//
// 对graph提取新的连接边片段
//

static int  opt_insert_edge_to_edge_seg_mark(int* id1,int*id2,int* edge_seg_mark,
    int i,int j)
{
    int re=0;
    if(edge_seg_mark[*id1]==i)
    {
        *id1=*id1-1;
        edge_seg_mark[*id1]=j;re=1;
    }
    else if(edge_seg_mark[*id1]==j)
    {
        *id1=*id1-1;
        edge_seg_mark[*id1]=i;re=1;
    }
    else if(edge_seg_mark[*id2]==i)
    {
        *id2=*id2-1;
        edge_seg_mark[*id2]=j;re=1;
    }
    else if(edge_seg_mark[*id2]==j)
    {
        *id2=*id2-1;
        edge_seg_mark[*id2]=i;re=1;
    }
    return re;
}

static void  opt_get_new_cut_eddge_graph(Sub_Poly_Ver*spvs,int len,
    Sub_Poly_Ver* bound,int bound_len,
    int* id1,int*id2,int* edge_seg_mark,int**edges_graph)
{
    *id1=len;*id2=len;
    int idn=-1;
    for(int i=0;i<len;i++)
    {
        if(edges_graph[i][i]>=1)
        {
            idn=i;
            for(int j=0;j<len;j++)
            {
                if(i!=j&&edges_graph[i][j]==1)
                { 
                    edges_graph[i][i]--;edges_graph[j][j]--;
                    edges_graph[i][j]=0;edges_graph[j][i]=0;
                    if(*id1==len&&*id2==len)
                    {
                        *id1=len-1;
                        edge_seg_mark[*id1]=j;edge_seg_mark[*id2]=i;
                        if(is_subv_in_polygon(spvs[i],bound,bound_len))
                        {
                            break;
                        }
                    }
                    else
                    {
                        *id2=len+1;
                        edge_seg_mark[*id2]=j;
                        //opt_insert_edge_to_edge_seg_mark(id1,id2,edge_seg_mark,i,j);
                    }
                    if(*id2-*id1==2){break;}
                }
            }
            break;
        }
    }

    if(idn!=-1)
    {
        int flag=1;
        while(flag)
        {
            flag=0;
            idn=edge_seg_mark[*id1];
            if(edges_graph[idn][idn]>=1&&!is_subv_in_polygon(spvs[idn],bound,bound_len))
            {
                flag=1;
                for(int i=0;i<len;i++)
                {
                    if(i!=idn&&edges_graph[idn][i]==1)
                    {
                        edges_graph[idn][idn]--;edges_graph[i][i]--;
                        edges_graph[idn][i]=0;edges_graph[i][idn]=0;
                        *id1=*id1-1;
                        edge_seg_mark[*id1]=i;
                        break;
                    }
                }

            }
            if(edge_seg_mark[*id1]==edge_seg_mark[*id2]){break;}

            idn=edge_seg_mark[*id2];
            if(edges_graph[idn][idn]>=1&&!is_subv_in_polygon(spvs[idn],bound,bound_len))
            {
                flag=1;
                for(int i=0;i<len;i++)
                {
                    if(i!=idn&&edges_graph[idn][i]==1)
                    {
                        edges_graph[idn][idn]--;edges_graph[i][i]--;
                        edges_graph[idn][i]=0;edges_graph[i][idn]=0;
                        *id2=*id2+1;
                        edge_seg_mark[*id2]=i;
                        break;
                    }
                }

            }
            if(edge_seg_mark[*id1]==edge_seg_mark[*id2]){break;}
        }
    }

}




static int opt_inset_edge_seg_mark2polygon(Sub_Poly_Ver*spvs,int len,
    Sub_Poly_Ver* bound,int bound_len,
    int id1,int id2,int* edge_seg_mark,
    double* n, 
    int** s,int *s_len)
{

    if(id1==id2)
    {
        subdivision_of_polygon1(bound,bound_len,s,n);
        *s_len=*s_len+bound_len-2;
        return 1;
    }

    if(edge_seg_mark[id1]==edge_seg_mark[id2]||!is_subv_in_polygon(spvs[edge_seg_mark[id1]],bound,bound_len)||
        !is_subv_in_polygon(spvs[edge_seg_mark[id2]],bound,bound_len))
    {   
        int i=id1;
        Sub_Poly_Ver edge[2];int flag=0;
        for(;i<id2;i++)
        {
            edge[0]=spvs[edge_seg_mark[i]];edge[1]=spvs[edge_seg_mark[i+1]];
            if(flag=0){
                flag=insert_one_edge2_polygon(spvs,len, n,s,
                    s_len,edge,bound,bound_len);
            }
            else
            {
                insert_one_edge2_mesh(spvs,len,n, s,
                    s_len,edge);
            }
        }
        if(flag==0){
            subdivision_of_polygon1(bound,bound_len,s,n);
            *s_len=*s_len+bound_len-2;
        }
        return 1;
    }

   
    Sub_Poly_Ver* polygon1=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(bound_len+id2-id1));
    Sub_Poly_Ver* polygon2=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*(bound_len+id2-id1));
    int p_len1=0,p_len2=0;
    for(int i=id1;i<=id2;i++)
    {
        polygon1[p_len1]=spvs[edge_seg_mark[i]];
        p_len1++;
    }
    p_len2=p_len1;
    for(int i=0;i<p_len1;i++)
    {
        polygon2[i]=polygon1[p_len1-1-i];
    }

    for(int i=0;i<bound_len;i++)
    {
        if(bound[i].i==edge_seg_mark[id2])
        {
            for(int j=0;j<bound_len;j++)
            {
                if(bound[(i+j+1)%bound_len ].i==edge_seg_mark[id1])
                {
                    break;
                }
                polygon1[p_len1]=bound[(i+j+1)%bound_len ];
                p_len1++;

            }
            break;
        }
    }

    for(int i=0;i<bound_len;i++)
    {
        if(bound[i].i==edge_seg_mark[id1])
        {
            for(int j=0;j<bound_len;j++)
            {
                if(bound[(i+j+1)%bound_len ].i==edge_seg_mark[id2])
                {
                    break;
                }
                polygon2[p_len2]=bound[(i+j+1)%bound_len ];
                p_len2++;

            }
            break;
        }
    }
    subdivision_of_polygon1(polygon1,p_len1,&(s[*s_len]),n);
    //tiaozheng_boundaries_tris( polygon1,p_len1,&(s[*s_len]), n);
    //printf("once\n");
    *s_len=*s_len+p_len1-2;

    subdivision_of_polygon1(polygon2,p_len2,&(s[*s_len]),n);
    //tiaozheng_boundaries_tris( polygon2,p_len2,&(s[*s_len]), n);

    *s_len=*s_len+p_len2-2;
    free(polygon1);free(polygon2);

    return 1;
}

static int opt_insert_all_edges2_polyon(Sub_Poly_Ver*spvs,int len,
    Sub_Poly_Ver* bound,int bound_len,
    int id1,int id2,int**edges_graph,
    double* n, 
    int** s,int *s_len)
{
    if(id1==-1||edges_graph==NULL)
    {
        // optimization_subdivision_of_polygon1(bound,bound_len,s,n);
        // *s_len=*s_len+bound_len-2;
        return 0;
    }
    for(int i=0;i<bound_len;i++)
    {
        if( (id1==bound[i].i&&id2==bound[(i+1)%bound_len].i)||
            (id2==bound[i].i&&id1==bound[(i+1)%bound_len].i)  )
        {
            return 0;
        } 
    }

    if(is_subv_in_polygon(spvs[id1],bound,bound_len)&&
        is_subv_in_polygon(spvs[id2],bound,bound_len))
    {


   

    }
    else
    {
        
// static int insert_one_edge2_polygon(Sub_Poly_Ver*spvs,int len, double* n,int** s,
//     int *s_len,Sub_Poly_Ver* edge,Sub_Poly_Ver* polygon,int p_len)
        // for(int i=1;i<len;i++)
        // {
        //     for(int j=0;j<i;j++)
        //     {
        //         if(edges_graph[i][j]==1)
        //         {
        //             Sub_Poly_Ver spvs_edge[2];
        //             spvs_edge[0]=spvs[i];
        //             spvs_edge[1]=spvs[j];
        //             // printf("insert edge:%d %d\n",edges[i][0],edges[i][1]);
        //             insert_one_edge2_mesh(spvs,len,n, s,
        //                 s_len,spvs_edge);
        //         }
        //     }
        // }
        // return ;

    }

}

static void optimization_insert_one_edge2_mesh(Sub_Poly_Ver*spvs,int len,double* n, int** s,
    int *s_len,int**edges_graph,Sub_Poly_Ver* bound,int bound_len)
{
    int id1=-1,id=-1,id2=-1;
    for(int i=0;i<len;i++)
    {
        if(edges_graph[i][i]!=2||is_subv_in_polygon(spvs[i],bound,bound_len)) {continue;}

        if(is_optimization_point_edge_id(spvs,edges_graph,len,i,&id1,&id2,bound,bound_len))
        {
            id=i;
            break;
        }
    }
    if(id==-1||id2==-1)
    {
        for(int i=1;i<len;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(edges_graph[i][j]==1)
                {
                    Sub_Poly_Ver spvs_edge[2];
                    spvs_edge[0]=spvs[i];
                    spvs_edge[1]=spvs[j];
                    // printf("insert edge:%d %d\n",edges[i][0],edges[i][1]);
                    insert_one_edge2_mesh(spvs,len,n, s,
                        s_len,spvs_edge);
                }
            }
        }
        return ;
    }
    assert(id1<len);assert(id2<len);
    edges_graph[id][id]=0;edges_graph[id][id1]=0;edges_graph[id][id2]=0;
    edges_graph[id1][id]=0;edges_graph[id2][id]=0;
    if(edges_graph[id1][id2]==1){edges_graph[id1][id1]--;edges_graph[id2][id2]--;}
    edges_graph[id1][id2]=1;edges_graph[id2][id1]=1;
    optimization_insert_one_edge2_mesh(spvs,len,n, s,
        s_len,edges_graph,bound,bound_len);
    int sz_len=0;
    for(int i=0;i<*s_len;i++)
    {
        if((s[i][0]==id2&&s[i][1]==id1)||(s[i][0]==id1&&s[i][1]==id2) )
        {
            s[*s_len+sz_len][0]=id;s[*s_len+sz_len][1]=s[i][1];s[*s_len+sz_len][2]=s[i][2];
            s[i][1]=id;sz_len++;
        }
        else if((s[i][1]==id2&&s[i][2]==id1)||(s[i][1]==id1&&s[i][2]==id2) )
        {
            s[*s_len+sz_len][0]=s[i][0];s[*s_len+sz_len][1]=id;s[*s_len+sz_len][2]=s[i][2];
            s[i][2]=id;sz_len++;
        }
        else if((s[i][2]==id2&&s[i][0]==id1)||(s[i][2]==id1&&s[i][0]==id2) )
        {
            s[*s_len+sz_len][0]=s[i][0];s[*s_len+sz_len][1]=s[i][1];s[*s_len+sz_len][2]=id;
            s[i][0]=id;sz_len++;
        }
    }

    *s_len=*s_len+sz_len;
}

static void youhua_boudnries_illegal_tris(int* bound,int bound_len,int** s,int* re_len)
{
    for(int i=0;i<bound_len;i++)
    {
        int num=0;
        for(int j=0;j<*re_len;j++)
        {
            if((s[j][0]==bound[i]&&s[j][1]==bound[(i+1)%bound_len])
                ||(s[j][1]==bound[i]&&s[j][2]==bound[(i+1)%bound_len])
                ||(s[j][2]==bound[i]&&s[j][0]==bound[(i+1)%bound_len]) )
            {
                num++;
                if(num>=2)
                {
                    s[j][0]=s[*re_len-1][0];s[j][1]=s[*re_len-1][1];s[j][2]=s[*re_len-1][2];
                    *re_len=*re_len-1;
                }
            }
        }
    }
}


static void opt_insert_edge_graph2polygon(Sub_Poly_Ver*spvs,int len,
    Sub_Poly_Ver* bound,int bound_len,
    double* n, int** s,
    int *s_len,
    int**edges_graph)
{
    int* edge_seg_mark=(int*)malloc(sizeof(int)*2*len);
    memset(edge_seg_mark,0,sizeof(int)*2*len);
    int id1=len,id2=len;
    opt_get_new_cut_eddge_graph(spvs,len,
            bound,bound_len,
            &id1,&id2,edge_seg_mark,edges_graph);

    opt_inset_edge_seg_mark2polygon(spvs,len,
        bound,bound_len,
        id1,id2,edge_seg_mark,
        n, 
        s,s_len);

    for(int i=1;i<len;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(edges_graph[i][j]==1)
            {
                Sub_Poly_Ver spvs_edge[2];
                spvs_edge[0]=spvs[i];
                spvs_edge[1]=spvs[j];
                    // printf("insert edge:%d %d\n",edges[i][0],edges[i][1]);
                insert_one_edge2_mesh(spvs,len,n, s,
                    s_len,spvs_edge);
            }
        }
    }
    free(edge_seg_mark);
}
        
        
        
int** optimization_subdivision_of_polygon_with_edges1(double** v,int len, 
    int* bound,int bound_len,int**edges,int edge_len,int* re_len)
{
    *re_len=0;
    if(len<3)
    {
        return NULL;
    }
    if(len==3)
    {
        if(bound_len<3){return NULL;}
        else
        {
            int ** re=(int**)malloc(sizeof(int*));
            re[0]=(int*)malloc(sizeof(int)*3);
            re[0][0]=bound[0];re[0][1]=bound[1];re[0][2]=bound[2];
            *re_len=1;
            return re;
        }
    }

    Sub_Poly_Ver* spvs=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*len);
    for(int i=0;i<len;i++)
    {
        spvs[i].p=v[i];
        spvs[i].i=i;
    }


    Sub_Poly_Ver* spvs_bound=(Sub_Poly_Ver*)malloc(sizeof(Sub_Poly_Ver)*bound_len);


    double **bound_v=(double**)malloc(sizeof(double*)*bound_len);

    for(int i=0;i<bound_len;i++)
    {
        spvs_bound[i]=spvs[bound[i]];
        bound_v[i]=v[bound[i]];
    }

    double * n=compute_plane_normal_of_jordan_curve(bound_v,bound_len);
    //normalize(n,3);
    free(bound_v);

    int ** re=(int**)malloc(sizeof(int*)*(bound_len+4*edge_len));

    for(int i=0;i<bound_len+4*edge_len;i++ )
    {
        re[i]=(int*)malloc(sizeof(int)*3);
        memset(re[i],0,sizeof(int)*3);
    }
    
    //subdivision_of_polygon1(spvs_bound,bound_len,re,n); 

    //optimization_subdivision_of_polygon1(spvs_bound,bound_len,re,n);
    

    if(edge_len>0&&edges!=NULL)
    {
        int**edges_graph=(int**)malloc(sizeof(int*)*len);
        for(int i=0;i<len;i++)
        {
            edges_graph[i]=(int*)malloc(sizeof(int)*len);
            memset(edges_graph[i],0,sizeof(int)*len);
        }
        for(int i=0;i<edge_len;i++)
        {
            assert(edges[i][0]<len);assert(edges[i][1]<len);
            if(edges_graph[edges[i][0]][edges[i][1]]==0)
            {
                edges_graph[edges[i][0]][edges[i][1]]=1;
                edges_graph[edges[i][1]][edges[i][0]]=1;
                edges_graph[edges[i][0]][edges[i][0]]++;
                edges_graph[edges[i][1]][edges[i][1]]++;
            }
        }
        opt_insert_edge_graph2polygon(spvs,len,
            spvs_bound,bound_len,
            n, re,
            re_len,
            edges_graph);
        //optimization_insert_one_edge2_mesh(spvs,len,n,re,re_len,edges_graph,spvs_bound,bound_len);
    
        for(int i=0;i<len;i++)
        {
            free(edges_graph[i]);
        }   
        free(edges_graph);
    }
    else
    {
        subdivision_of_polygon1(spvs_bound,bound_len,re,n);
        *re_len=bound_len-2;
    }
    
    //youhua_boudnries_illegal_tris(bound,bound_len,re,re_len);
    printf("shengyu :%d %d %d\n",bound_len+4*edge_len-*re_len,bound_len+4*edge_len,*re_len);
    show_sub_data(re,*re_len);
    assert(*re_len<bound_len+4*edge_len);
    for(int i=*re_len;i<bound_len+4*edge_len;i++)
    {
        free(re[i]);
    }

    free(spvs_bound);
    free(spvs);
    SAFE_FREE(n);
    return re;
}